package main.java.learning.directory.Work.排序.Tmt;

/**
 * @author: tianmingtai
 * @create: 2021/02/20 11:29
 * @description: 快速排序
 */

public class QuickSortDay2 {

    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1};
        quickSort(arr, 0, arr.length - 1);
        // 增强for快捷键 iter
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 起始位置
        int leftIndex = left;
        // 数组结束位置
        int rightIndex = right;
        // 基准值
        int key = arr[left];

        // 从左右交替扫描，知道左右指针left = right
        while (leftIndex < rightIndex) {
            // 1、从右往左扫描，找到第一个比基准值小的元素
            while (rightIndex > leftIndex && arr[rightIndex] >= key) {
                rightIndex--;
            }

            // 比基准值小的元素放在左边
            arr[leftIndex] = arr[rightIndex];

            // 2、从左往右扫描，找到第一个比基准值大的元素
            while (leftIndex < rightIndex && arr[leftIndex] <= key) {
                leftIndex++;
            }
            //找到了比基准值大的元素，放在右边
            arr[rightIndex] = arr[leftIndex];
        }

        // 基准值重置
        arr[rightIndex] = key;
        //对基准值左边的元素继续递归调用排序
        quickSort(arr, left, leftIndex - 1);
        // 对基准值右边的元素继续递归调用排序
        quickSort(arr, rightIndex + 1, right);
    }
}
